/**
 * @brief 堆的实现
 * @version 1.0
 * @author 宋炜
 */

#pragma once

#include <typte_traits>
#include <deque>  
#include <functional>  
#include <iterator>  
#include <utility>  
#include <vector>  
#include <algorithm>  

namespace wheels { namespace container{

template<typename Key, typename Value, bool isLess = true>  
class heap {  
public:  
	using key_type = Key;  
	using value_type = Value;  
	
private:  
	struct Node {  
		Key key;  
		Value value;  
  
		bool operator<(const Node& b) const { return key < b.key; }  
		bool operator>(const Node& b) const { return key > b.key; }  
	};  
  
	using Compare = std::conditional_t<isLess, std::less<Node>, std::greater<Node>>;  
  
private:  
	std::deque<Node> m_data__;  
	Compare m_cmp;  
  
public:  
	heap() : m_cmp(Compare()) {}  
	virtual ~heap() {}  
  
	void insert(const Key& key, const Value& value) {  
		Node node{key, value};  
		m_data__.push_back(node);  
		std::push_heap(m_data__.begin(), m_data__.end(), m_cmp);  
	}  
  
	std::pair<Key, Value> pop() {  
		std::pop_heap(m_data__.begin(), m_data__.end(), m_cmp);  
		Node top_node = m_data__.back();  
		m_data__.pop_back();  
		return std::make_pair(top_node.key, top_node.value);  
	}  
  
	bool empty() const {  
		return m_data__.empty();  
	}  
  
	size_t size() const {  
		return m_data__.size();  
	}  
  
	void erase(const Key& key) {  
		auto it = std::find_if(m_data__.begin(), m_data__.end(), [key](const Node& node) {  
			return node.key == key;  
		});  
		if (it != m_data__.end()) {  
			std::pop_heap(m_data__.begin(), it + 1, m_cmp);  
			m_data__.erase(it);  
			std::make_heap(m_data__.begin(), m_data__.end(), m_cmp);  
		}  
	}  
  
	/**
	 * @brief 查找指定key的内容
	 * @param key[ I ],要查找的键
	 * @return 返回对应的迭代器
	 */
	iterator find(const Key& key) {
		for( auto it = m_data__.begin(); it != m_data__.end(); ++it ){
			if( it->key == key ) return it;
		}

		return m_data__.end();
	}
	/**
	 * @brief 判断是否存在key为指定内容的数据
	 * @return key[ I ]， 要判断的键
	 */
	bool has( const Key& key ){
		for( auto it = m_data__.begin(); it != m_data__.end(); ++it ){
			if( it->key == key ) return true;
		}

		return false;
	}
  
  
	auto begin() { return m_data__.begin(); }  
	auto end() { return m_data__.end(); }  
};
	
}}
